#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

typedef vector<vector<size_t> > matrix;

void get_lcs(string &a, string &b)
{
    size_t m = a.size(), n = b.size();

    matrix lcslen(m+1);
    for (matrix::iterator it = lcslen.begin(); it != lcslen.end(); it++)
    {
	it->resize(n+1);
	(*it)[0] = 0;
    }

    fill(lcslen.begin()->begin(), lcslen.begin()->end(), 0);

    size_t i, j;
    for (i = 1; i <= m; i++) 
    {
	for (j = 1; j <= n; j++)
	{
	    if (a[i-1] == b[j-1])
	    {
		lcslen[i][j] = lcslen[i-1][j-1] + 1;
	    }
	    else
	    {
		lcslen[i][j] = (lcslen[i-1][j] > lcslen[i][j-1])?lcslen[i-1][j]:lcslen[i][j-1];
	    }
	}
    }

    if (!lcslen[m][n])
	cout << "No LCS" << endl;

    vector<size_t> ai, bi;
    ai.reserve(lcslen[m][n]);
    bi.reserve(lcslen[m][n]);

    i = m, j = n;
    while (i&&j)
    {
	if (lcslen[i][j] == lcslen[i-1][j])
	{
	    i--;
	}
	else if (lcslen[i][j] == lcslen[i][j-1])
	{
	    j--;
	}
	else
	{
	    ai.push_back(i);
	    bi.push_back(j);
	    i--;
	    j--;
	}
    }

    vector<size_t>::reverse_iterator ait = ai.rbegin(), bit = bi.rbegin(); 
    for (; ait != ai.rend(); ait++, bit++)
    {
	cout << a[*ait - 1] << "(" << *ait << "," << *bit << ")" << endl;
    }

}


int main(int argc, char* argv[])
{
    string a("ABCBDAB");
    string b("BDCABA");
    get_lcs(a, b);
    b = "YUUI";
    get_lcs(a, b);

    return 0;
}




